#define MOD 1000000007
class Solution {
public:
    long long int fib(int n) {
        if(n < 2){
            return n;
        }
        long long int f0 = 0;
        long long int f1 = 1;
        long long int ret = 1;
        while(n > 2){
            n--;
            f0 = f1;
            f1 = ret;
            ret = (f0+f1) % MOD;
        }
        return ret;
    }
};